package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/26 10:42
 * @description <p>两个链表的第 1 个重合节点 </p>
 */


/**
 * 题目：输入两个单向链表，请问如何找出它们的第 1 个重合节点。例
 * 如，图 4.5 中的两个链表的第 1 个重合节点的值是 4。
 */
public class toOffer4_3_23 {
    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        ListNode headB = new ListNode(1);
        System.out.println(getIntersectionNode(headA, headB).getVal());
    }

    /**
     * 思路：
     * 先找出两个链表的长度len1和len2，看哪个大，大的那个先走|len1-len2|步，然后两个链表同时走
     * 如果当前节点的下一个节点相同，那么下一个节点就是重合节点
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //判空
        if (headA == null || headB == null) {
            return null;
        }

        int len1 = count(headA);
        int len2 = count(headB);
        int dif = Math.abs(len1 - len2);

        if (len1 == Math.max(len1, len2)){
            for (int i = 0; i < dif; i++) {
                headA = headA.next;
            }
        }else {
            for (int i = 0; i < dif; i++) {
                headB = headB.next;
            }
        }
        while (headA != headB){
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
    }

    /**
     * 计算链表的节点数
     * @param node
     * @return
     */
    public static int count(ListNode node){
        int count = 0;
        while (node.next != null){
            count++;
            node = node.next;
        }
        return count;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public int getVal() {
            return this.val;
        }
    }
}
